Machine de Turing symétrique
En informatique théorique, une machine de Turing symétrique est une machine de Turing dont le graphe des configurations est non-orienté, c'est-à-dire qu'il est possible de passer d'une configuration A à une configuration B, si et seulement si l'opération inverse est possible.
Définition[modifier | modifier le code]
Une machine de Turing symétrique est une variante des machines de Turing classiques. Les transitions d'une machine de Turing symétrique sont de la forme (p,ab,D,cd,q), où p et q sont des états, a, b, c, d sont des lettres et D une direction de déplacement de la tête de lecture. Prenons par exemple D égual à droite, la transition (p,ab, D, cd, q) correspond à l'action décrite par la machine lorsque celle ci se trouve dans l'état p, a sa tête de lecture au-dessus de la lettre a, écrit c à la place de a, puis déplace sa tête de lecture d'une case vers la droite, au-dessus de la lettre b, écrit d à la place de b et passe dans l'état q. La transition inverse est aussi empruntable et vaut (q, cd, -D, ab, p). Le fait de changer les lettres deux par deux simplifie la définition mais n'est pas une nécessité.
Intérêt[modifier | modifier le code]
Les machines de Turing symétriques ont été introduites en 1982 par Harry R. Lewis et Christos Papadimitriou[1],[2], en cherchant à classer plus finement le problème USTCON, consistant à déterminer s'il existe ou non un chemin entre deux sommets quelconques s et t dans un graphe non-orienté. Ce problème était alors connu comme appartenant à NL, sans avoir pourtant besoin du non-déterminisme de la classe NL.
Références[modifier | modifier le code]
- Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
- Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. p. 161-187. 1982.
